{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #有序数组中的单一元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: singleNonDuplicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序数组中的单一元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个只包含整数的有序数组 <code>nums</code>&nbsp;，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,1,2,3,3,4,4,8,8]\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums =  [3,3,7,7,10,11,11]\n",
    "<strong>输出:</strong> 10\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i]&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶:</strong>&nbsp;采用的方案可以在 <code>O(log n)</code> 时间复杂度和 <code>O(1)</code> 空间复杂度中运行吗？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 540&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/single-element-in-a-sorted-array/\">https://leetcode-cn.com/problems/single-element-in-a-sorted-array/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [skFtm2](https://leetcode.cn/problems/skFtm2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [skFtm2](https://leetcode.cn/problems/skFtm2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        lo, hi = 0, len(nums) - 1\n",
    "        while lo < hi:\n",
    "            mid = 2 * ((lo + hi) // 4)\n",
    "            if nums[mid] == nums[mid+1]:\n",
    "                lo = mid+2\n",
    "            else:\n",
    "                hi = mid\n",
    "        return nums[lo]\n",
    "        \n",
    "        \n",
    "\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        l=0\n",
    "        h=len(nums)-1\n",
    "        while l<h:\n",
    "            mid=int(l+(h-l)/2)\n",
    "            if mid%2==1:\n",
    "                mid-=1\n",
    "            if nums[mid]==nums[mid+1]:\n",
    "                l=mid+2\n",
    "            else:\n",
    "                h=mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        \n",
    "        start,end=0,len(nums)-1\n",
    "        mid=(start+end)//2\n",
    "        frontnums,rearnums=deque(nums[:mid]),deque(nums[mid:])\n",
    "        if frontnums[-1]==rearnums[0]:\n",
    "            if len(frontnums)>len(rearnums):\n",
    "                rearnums.appendleft(frontnums.pop())\n",
    "            else:frontnums.append(rearnums.popleft())\n",
    "            \n",
    "        if len(frontnums)%2==1:\n",
    "            newnums=self.singleNonDuplicate(list(frontnums))\n",
    "        if len(rearnums)%2==1:\n",
    "            newnums=self.singleNonDuplicate(list(rearnums))\n",
    "            \n",
    "        return newnums\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return reduce(operator.xor,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        set_nums = set(nums)\n",
    "        \n",
    "        return sum(set_nums)*2 -sum(nums)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        N=len(nums)\n",
    "        if N==0:\n",
    "            return nums[0]\n",
    "        if nums[0]!=nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[N-2]!=nums[N-1]:\n",
    "            return nums[N-1]\n",
    "        l=0\n",
    "        r=N-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if (mid+1)%2==0 and nums[mid]==nums[mid-1]:\n",
    "                l=mid+1\n",
    "            elif (mid+1)%2==1 and nums[mid]==nums[mid+1]:\n",
    "                l=mid+2\n",
    "            else:\n",
    "                r=mid\n",
    "        return nums[l]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        return sum(nums[::2])*2-sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: list) -> int:\n",
    "        l = []\n",
    "        while nums:\n",
    "            a = nums.pop()\n",
    "            b = True\n",
    "            for i in range(0, len(l)):\n",
    "                if a == l[i]:\n",
    "                    l.pop(i)\n",
    "                    b = False\n",
    "                    break\n",
    "            if b:\n",
    "                l.append(a)\n",
    "        return l[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums) -1\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i <= n:\n",
    "            if len(stack) == 0:\n",
    "                x = nums.pop()\n",
    "                stack.append(x)\n",
    "                i += 1\n",
    "                continue\n",
    "            x = nums.pop()\n",
    "            if x in stack:\n",
    "                stack.pop()\n",
    "                i += 1\n",
    "            else:\n",
    "                stack.append(x)\n",
    "                i += 1\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # 方法1、哈希表\n",
    "        # 方法2、数学\n",
    "        # 方法3、二分查找\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if nums[0]!=nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[-1]!=nums[-2]:\n",
    "            return nums[-1]\n",
    "        left,right = 0,len(nums)-1\n",
    "        while left<=right:\n",
    "            middle = (left+right)//2\n",
    "            if nums[middle]==nums[middle+1]:\n",
    "                if middle%2==0:\n",
    "                    left=middle+1\n",
    "                else:\n",
    "                    right=middle-1\n",
    "            elif nums[middle]==nums[middle-1]:\n",
    "                if middle%2==0:\n",
    "                    right = middle-1\n",
    "                else:\n",
    "                    left = middle+1\n",
    "            else:\n",
    "                return nums[middle]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        return sum(set(nums)) * 2 - sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        lo = 0\n",
    "        hi = len(nums) - 1\n",
    "        while lo < hi:\n",
    "            mid = (hi- lo)//2 + lo\n",
    "            if nums[mid] == nums[mid+1]:\n",
    "                halves_are_even = (hi - mid -1) % 2 == 1\n",
    "                if halves_are_even:\n",
    "                    lo = mid + 2\n",
    "                else:\n",
    "                    hi = mid - 1\n",
    "            elif nums[mid] == nums[mid-1]:\n",
    "                halves_are_even = (hi - mid) % 2 == 1\n",
    "                if halves_are_even:\n",
    "                    lo = mid + 1\n",
    "                else:\n",
    "                    hi = mid - 2\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        return nums[lo]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # 方法一\n",
    "        numsdic = collections.Counter(nums)\n",
    "        data = sorted(numsdic.items(), key = lambda x: x[1])\n",
    "        return data[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        lo,hi = 0,len(nums)-1\n",
    "        while lo<hi:\n",
    "            mid = lo+(hi-lo)//2\n",
    "            iseven = (hi-mid)%2==0\n",
    "            if nums[mid]==nums[mid+1]:\n",
    "                if iseven:\n",
    "                    lo =mid+2\n",
    "                else:\n",
    "                    hi =mid-1\n",
    "            elif nums[mid-1]==nums[mid]:\n",
    "                if iseven:\n",
    "                    hi=mid-2\n",
    "                else:\n",
    "                    lo=mid+1\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        return nums[lo]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if mid%2==1:\n",
    "                mid-=1\n",
    "            if nums[mid]==nums[mid+1]:\n",
    "                left=mid+2\n",
    "            else:\n",
    "                right=mid\n",
    "        return nums[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        k = 0\n",
    "        j = len(nums) - 1\n",
    "        while k < j:\n",
    "            m = k + (j-k)//2\n",
    "            b = (j-m)%2 == 0\n",
    "            if nums[m] == nums[m+1]:\n",
    "                if b:\n",
    "                    k = m + 2\n",
    "                else:\n",
    "                    j = m - 1\n",
    "            elif nums[m] == nums[m-1]:\n",
    "                if b:\n",
    "                    j = m - 2\n",
    "                else:\n",
    "                    k = m + 1\n",
    "            else:\n",
    "                return nums[m]\n",
    "        return nums[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "\n",
    "        if nums[l]!=nums[l+1]:\n",
    "            return nums[l]\n",
    "        if nums[r]!=nums[r-1]:\n",
    "            return nums[r]\n",
    "\n",
    "        while l<r:\n",
    "            mid=int(l+(r-l)/2)\n",
    "            check = (mid-l)%2==0 #odd\n",
    "\n",
    "            if nums[mid]!=nums[mid-1] and nums[mid]!=nums[mid+1]:\n",
    "                return nums[mid]\n",
    "            elif nums[mid]!=nums[mid+1]:\n",
    "                if check:\n",
    "                    r=mid-2\n",
    "                else:\n",
    "                    l=mid+1\n",
    "            else:\n",
    "                if check:\n",
    "                    l=mid+2\n",
    "                else:\n",
    "                    r=mid-1\n",
    "\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        nums_count = dict(collections.Counter(nums))\n",
    "        sort_nums_count = sorted(nums_count.items(), key=lambda x:x[1])\n",
    "        return sort_nums_count[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = set(nums[i] for i in range(0,len(nums),2))-set(nums[i] for i in range(1,len(nums),2))\n",
    "        return tuple(res)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#输入: nums =  [3,3,7,7,10,11,11]\n",
    "#输出: 10\n",
    "#哈希表\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        new_list=[]\n",
    "        new_list2=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in new_list:\n",
    "                new_list.append(nums[i])\n",
    "            elif nums[i] in new_list:\n",
    "                new_list2.append(nums[i]) \n",
    "        x=list(set(new_list)^set(new_list2)) \n",
    "        return x[0]   \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        even = [nums[i] for i in range(0,len(nums),2)]\n",
    "        odd = [nums[i] for i in range(1,len(nums)-1,2)]\n",
    "        return (set(even) ^ set(odd)).pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def _method1(self, nums):\r\n",
    "        low, high = 0, len(nums)-1\r\n",
    "\r\n",
    "        while low < high:\r\n",
    "            middle = low+(high-low)//2\r\n",
    "            halvesAreEven = (high-middle)%2 == 0\r\n",
    "            if nums[middle+1] == nums[middle]:\r\n",
    "                if halvesAreEven:\r\n",
    "                    low = middle+2\r\n",
    "                else:\r\n",
    "                    high = middle-1\r\n",
    "            elif nums[middle-1] == nums[middle]:\r\n",
    "                if halvesAreEven:\r\n",
    "                    high = middle-2\r\n",
    "                else:\r\n",
    "                    low = middle+1\r\n",
    "            else:\r\n",
    "                return nums[middle]\r\n",
    "\r\n",
    "        return nums[low]\r\n",
    "\r\n",
    "    def _method2(self, nums: List[int]) -> int:\r\n",
    "        if len(nums) == 1:\r\n",
    "            return nums[0]\r\n",
    "        while len(nums) > 1:\r\n",
    "            i = nums.pop()\r\n",
    "            j = nums.pop()\r\n",
    "            if i != j:\r\n",
    "                return i\r\n",
    "            else:\r\n",
    "                return self._method2(nums)\r\n",
    "\r\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\r\n",
    "        return self._method2(nums)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums):\n",
    "            res=nums.pop(0)\n",
    "            while len(nums)>=2:\n",
    "                tmp=nums.pop()^nums.pop(0)\n",
    "                res=res^tmp\n",
    "            return res\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if nums[-1]-nums[-2]:\n",
    "            return nums[-1]\n",
    "        for i in range(0,len(nums)-1):\n",
    "            nums[i]-=nums[i+1]\n",
    "            if nums[i]!=0 and (nums[i+1]-nums[i+2]==0) and nums[i-1]!=0:\n",
    "                return nums[i]+nums[i+1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            res^=x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans ^= num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        return nums[bisect_left(range(len(nums) - 1), True, key=lambda x: nums[x] != nums[x ^ 1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        def run(l, r):\n",
    "            mid = (l + r) // 2\n",
    "            if nums[mid-1] < nums[mid] < nums[mid+1]:\n",
    "                return nums[mid]\n",
    "            \n",
    "            if mid % 2:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    return run(l, mid-1)\n",
    "                else:\n",
    "                    return run(mid + 1, r)\n",
    "            else:\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    return run(l, mid-1)\n",
    "                else:\n",
    "                    return run(mid + 1, r)\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if nums[0] != nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[-1] != nums[-2]:\n",
    "            return nums[-1]\n",
    "        return run(0, len(nums) - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        sidelen = len(nums) // 2\n",
    "        mid = sidelen\n",
    "        while sidelen:\n",
    "            if nums[mid] ^ nums[mid-1] and nums[mid] ^ nums[mid+1]: break\n",
    "            flag = sidelen % 2\n",
    "            sidelen = sidelen // 2\n",
    "            if nums[mid] == nums[mid-1]:\n",
    "                mid = mid + (sidelen + 1) * (1 if flag else -1)\n",
    "            else:\n",
    "                mid = mid - (sidelen + 1) * (1 if flag else -1)\n",
    "            sidelen -= (flag == 0)\n",
    "        return nums[mid]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if nums[mid] == nums[mid^1]:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        def left_or_right(num):\n",
    "            l = len(num)\n",
    "            #if l == 3\n",
    "            i = l // 2\n",
    "            if i % 2 == 0:\n",
    "                if num[i] == num[i-1]:\n",
    "                    return -1\n",
    "                elif num[i] == num[i+1]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                if num[i] == num[i-1]:          #[1,2,2]\n",
    "                    return 1\n",
    "                elif num[i] == num[i+1]:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 0\n",
    "        x = length\n",
    "        new_num = nums\n",
    "        while len(new_num) > 2 :\n",
    "            res = left_or_right(new_num)\n",
    "            L = len(new_num)//2\n",
    "            if res == -1:\n",
    "                if L == 1 :\n",
    "                    return new_num[0]\n",
    "                elif L % 2 == 0:\n",
    "                    new_num = new_num[:L+1]\n",
    "                else:\n",
    "                    new_num = new_num[:L]\n",
    "            elif res == 1:      #[2]\n",
    "                if L==1:\n",
    "                    return new_num[2]\n",
    "                elif L % 2 == 0:\n",
    "                    new_num = new_num[L:]  # [2,2,3,3,4,4,5,6,6,7,7]\n",
    "                else:\n",
    "                    new_num = new_num[L+1:]     \n",
    "            else:\n",
    "                return new_num[L]    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        #如果mid是偶数，比较nums[mid]和nums[mid+1]是否一样\n",
    "        #如果mid是奇数，比较nums[mid]和nums[]mid-1]是否一样\n",
    "        n=0\n",
    "        for i in nums:\n",
    "            n^=i\n",
    "        return (n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # a = nums[0]\n",
    "        # for b in nums[1:]:\n",
    "        #     a = a ^ b\n",
    "\n",
    "        # return(a)\n",
    "\n",
    "        ###### (3) ######\n",
    "        n = len(nums)\n",
    "        if n ==1:\n",
    "            return(nums[0])\n",
    "        \n",
    "        ## 只统计奇数，因为奇数 不会出现 可对可错 ##\n",
    "        # 所以干脆 套两层i\n",
    "        # 第一层i*2+1 才是真 i\n",
    "        L,R = 0,n//2-1\n",
    "        print(L,R)\n",
    "        while L<=R:\n",
    "            M = (L+R)//2\n",
    "            # 这才是真的M，上面的M、L、R 只是为了方便移动，确保只出奇数\n",
    "            M2 = M*2+1\n",
    "            if nums[M2-1] == nums[M2]:\n",
    "                L = M+1\n",
    "            else:\n",
    "                R = M-1\n",
    "        L2 = L*2+1\n",
    "        \n",
    "        return(nums[L2-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        a = nums[0]\n",
    "        for b in nums[1:]:\n",
    "            a = a ^ b\n",
    "\n",
    "        return(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1 or nums[0] != nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[n - 1] != nums[n - 2]:\n",
    "            return nums[n - 1]\n",
    "        left, right = 0, n - 1\n",
    "        while right - left > 1:\n",
    "            mid = left + (right - left) // 2\n",
    "            if nums[mid] != nums[mid + 1] and nums[mid] != nums[mid - 1]:\n",
    "                return nums[mid]\n",
    "            if ((nums[mid] == nums[mid + 1] and mid % 2 == 0)\n",
    "                    or (nums[mid] == nums[mid - 1] and mid % 2 == 1)):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        if nums[left] != nums[left - 1] and nums[left] != nums[left + 1]:\n",
    "            return nums[left]\n",
    "        return nums[right]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        dic = dict(collections.Counter(nums))\n",
    "        dic = sorted(dic.items(),key = lambda x: x[1])\n",
    "        return dic[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 一次查看两个元素\n",
    "    def singleNonDuplicate(self, nums: list) -> int:\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if i == len(nums) - 1:\n",
    "                return nums[i]\n",
    "            if nums[i] != nums[i + 1]:\n",
    "                return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # 在nums的最前面添加-inf，最后面添加inf\n",
    "        nums.insert(0, -inf)\n",
    "        nums.append(inf)\n",
    "        # 二分查找确定在哪一边\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "\n",
    "        ans = 0\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            # 如果mid既不等于左边，也不等于右边，那么此时的值就是单一的值\n",
    "            if nums[mid + 1] > nums[mid] > nums[mid - 1]:\n",
    "                ans = nums[mid]\n",
    "                break\n",
    "            elif nums[mid] == nums[mid - 1]:\n",
    "                if (mid - left) & 1 == 0:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid + 1\n",
    "            else:\n",
    "                if (right - mid) & 1 == 0:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        s = nums[0]\n",
    "        for i in nums[1:]:\n",
    "            s ^= i\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        for i in range(1, len(nums), 2):\n",
    "            if nums[i]-nums[i-1] != 0:\n",
    "                return nums[i-1]\n",
    "        return nums[len(nums)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        for num in nums:\n",
    "            nums.remove(num)\n",
    "            if num in nums:\n",
    "                continue\n",
    "            else:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.append(-1)\n",
    "        for i in range(0,n,2):\n",
    "            if nums[i] == nums[i+1]:\n",
    "                continue\n",
    "            else:\n",
    "                return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l, r = 0, len(nums)-1\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            if nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]:\n",
    "                return nums[mid]\n",
    "            elif nums[mid] == nums[mid^1]:\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            m = (i + j) // 2\n",
    "            if nums[m] == nums[m ^ 1]:\n",
    "                i = m + 1\n",
    "            else:\n",
    "                j = m\n",
    "        return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            result ^= num\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if mid % 2 == 0:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            else:\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    left = mid +1\n",
    "                else:\n",
    "                    right = mid\n",
    "        return nums[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        r = n - 1\n",
    "        \n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid % 2 == 0:\n",
    "                if mid < n -1 and nums[mid] == nums[mid + 1]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "                \n",
    "            else:\n",
    "                if mid > 0 and nums[mid] == nums[mid - 1]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "      \n",
    "        return nums[r]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        low, high = 0, len(nums) - 1 # low, high: 那个唯一数的下标\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            mid -= mid & 1\n",
    "            if nums[mid] == nums[mid + 1]:\n",
    "                low = mid + 2\n",
    "            else:\n",
    "                high = mid\n",
    "        return nums[low]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i < n-1 and nums[i] == nums[i+1]:\n",
    "            i += 2\n",
    "        return nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        return reduce(lambda x, y: x ^ y, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if mid < n - 1 and nums[mid] == nums[mid + 1]:\n",
    "                mid += 1\n",
    "\n",
    "            if mid & 1:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                if mid == 0 or nums[mid] != nums[mid - 1]:\n",
    "                    return nums[mid]\n",
    "                r = mid - 2\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        l, r = 0, n - 1\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            if nums[mid] == nums[mid ^ 1]:\n",
    "                # nums 为奇数时, mid - 1 == mid ^ 1\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        i,j = 0,len(nums)-1\n",
    "        while i<j:\n",
    "            mid = (i+j)//2\n",
    "            if nums[mid] != nums[mid ^ 1]:\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid+1\n",
    "        return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # k = 0\n",
    "        # res = 0\n",
    "        # for i in range(len(nums)):\n",
    "        #     if k == 0:\n",
    "        #         res += nums[i]\n",
    "        #         k = 1\n",
    "        #     else:\n",
    "        #         res -= nums[i]\n",
    "        #         k = 0\n",
    "        # return res\n",
    "\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res ^= num\n",
    "            print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if mid % 2 == 0:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    left = mid + 2\n",
    "                else:\n",
    "                    right = mid\n",
    "            else:\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        return nums[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i < n-1 and nums[i] == nums[i+1]:\n",
    "            i += 2\n",
    "        return nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        low, high = 0, len(nums) - 1\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            mid -= mid & 1\n",
    "            if nums[mid] == nums[mid + 1]:\n",
    "                low = mid + 2\n",
    "            else:\n",
    "                high = mid\n",
    "        return nums[low]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = nums[0]\n",
    "        for x in nums[1:]:\n",
    "            res ^= x\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        for n in nums:\n",
    "            s ^= n\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            res ^= x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            res ^= x\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        for i in range(0,len(nums)-1,2):\n",
    "            if nums[i]!=nums[i+1]:\n",
    "                return nums[i]\n",
    "        \n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if i + 1 > len(nums) - 1:\n",
    "                return nums[i]\n",
    "            if nums[i] != nums[i + 1]:\n",
    "                return nums[i]\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for n in nums:\n",
    "            ans^=n\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if mid % 2 == 0:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    left = mid + 2\n",
    "                else:\n",
    "                    right = mid\n",
    "            else:\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "        return nums[left]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        for i in range(0, len(nums), 2):\n",
    "            if (i+1) >= len(nums) or nums[i] != nums[i+1]:\n",
    "                return nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)>=2:\n",
    "            i = 0\n",
    "            while i < len(nums)-1:\n",
    "                if nums[i] !=nums[i+1]:\n",
    "                    return nums[i]\n",
    "                i+=2\n",
    "            return nums[-1]\n",
    "        else:\n",
    "            return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[-1]\n",
    "\n",
    "        for i in range(0,len(nums)-1,2):\n",
    "            if nums[i]!=nums[i+1]:\n",
    "                return nums[i]\n",
    "        \n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l,r=0,len(nums)-1\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if nums[mid]==nums[mid^1]:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i < n-1 and nums[i] == nums[i+1]:\n",
    "            i += 2\n",
    "        return nums[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        n = len(nums)\n",
    "        r = n - 1\n",
    "        \n",
    "\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid % 2 == 0:\n",
    "                if mid < n -1 and nums[mid] == nums[mid + 1]:\n",
    "                    l = mid + 2\n",
    "                else:\n",
    "                    r = mid\n",
    "                \n",
    "            else:\n",
    "                if mid > 0 and nums[mid] == nums[mid - 1]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "      \n",
    "        return nums[r]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mid % 2 != 0 and mid + 1 < len(nums):\n",
    "                if nums[mid] == nums[mid + 1]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            elif mid % 2 == 0 and mid + 1 < len(nums):\n",
    "                if nums[mid] != nums[mid + 1]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        return nums[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1 or nums[0] != nums[1]:\n",
    "            return nums[0]\n",
    "        if nums[length-1] != nums[length-2]:\n",
    "            return nums[length-1]\n",
    "        left, right = 0, length-1\n",
    "        while left <= right:\n",
    "            middle = (right + left) // 2\n",
    "            if nums[middle] != nums[middle+1] and nums[middle] != nums[middle-1]:\n",
    "                return nums[middle]\n",
    "            elif middle % 2 == 0:\n",
    "                if nums[middle] == nums[middle-1]:\n",
    "                    right = middle - 1\n",
    "                else:\n",
    "                    left = middle\n",
    "            else:\n",
    "                if nums[middle] == nums[middle-1]:\n",
    "                    left = middle\n",
    "                else:\n",
    "                    right = middle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums)-1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            # 找到一个中间点，看坐标是奇数还是偶数\n",
    "            if mid%2 == 0:\n",
    "                # 如果是偶数坐标\n",
    "                # 如果左侧数据等于它那么，right = mid -2;\n",
    "                # 如果右侧数据等于它，那么，left = mid + 2;\n",
    "                if mid >= 1 and nums[mid] == nums[mid-1]:\n",
    "                    right = mid - 2\n",
    "                    continue\n",
    "                if mid+1 < len(nums) and nums[mid] == nums[mid+1]:\n",
    "                    left = mid + 2\n",
    "                    continue\n",
    "                return nums[mid]\n",
    "            if mid%2 == 1:\n",
    "                # 如果是奇数坐标，如果左侧等于它，那么 left = mid+1; 如果右侧等于它，那么 right = mid-1\n",
    "                if nums[mid] == nums[mid-1] and mid >= 1:\n",
    "                    left = mid + 1\n",
    "                    continue\n",
    "                if nums[mid] == nums[mid+1] and mid+1 < len(nums):\n",
    "                    right = mid - 1\n",
    "                    continue\n",
    "                return nums[mid]\n",
    "\n",
    "        return nums[left]\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        low, high = 0, len(nums) - 1\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if mid % 2 == 0:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    low = mid + 1\n",
    "                else:\n",
    "                    high = mid\n",
    "            else:\n",
    "                if nums[mid-1] == nums[mid]:\n",
    "                    low = mid + 1\n",
    "                else:\n",
    "                    high = mid\n",
    "        return nums[low]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if nums[i]!=nums[i-1] and nums[i]!=nums[i+1]:\n",
    "                return nums[i]\n",
    "        if nums[0]!=nums[1]:\n",
    "            return nums[0]\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        while left < right:\n",
    "            middle = int(left+(right-left)/2)\n",
    "            if middle%2 == 1:\n",
    "                if nums[middle] == nums[middle-1]:\n",
    "                    left = middle+1\n",
    "                else: \n",
    "                    right = middle #mid匹配不上，则mid也可能是解\n",
    "            if middle%2 == 0:\n",
    "                if len(nums) == 1:\n",
    "                    return nums[0]\n",
    "                if nums[middle] == nums[middle+1]:\n",
    "                    left = middle+1\n",
    "                else:\n",
    "                    right = middle\n",
    "        return nums[left]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        eor = 0\n",
    "        for num in nums:\n",
    "            eor^=num\n",
    "        return eor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = len(nums)-1\n",
    "        while l < r:\n",
    "            m = (l+r) // 2\n",
    "            m -= m & 1\n",
    "            if nums[m] == nums[m+1]:\n",
    "                l = m + 2\n",
    "            else:\n",
    "                r = m\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        start,end=0,len(nums)-1\n",
    "        while(start<end):\n",
    "          mid=(end+start)//2\n",
    "          if nums[mid]==nums[mid^1]:\n",
    "            start=mid+1\n",
    "          else:\n",
    "            end=mid\n",
    "        return nums[start]\n",
    "          \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        while l < r:\n",
    "            mid = l + (r-l)//2 \n",
    "            \n",
    "            if mid % 2 == 0:\n",
    "                if nums[mid] == nums[mid+1]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            else:\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    l = mid + 1 \n",
    "                else:\n",
    "                    r = mid\n",
    "        \n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        i,j=0,1\n",
    "        while j<n:\n",
    "            if not nums[i]==nums[j]:\n",
    "                return nums[i]\n",
    "            i+=2\n",
    "            j+=2\n",
    "        return nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        while l < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if nums[m] == nums[m ^ 1]:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        \n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if mid % 2 != 0 and mid + 1 < len(nums):\n",
    "                if nums[mid] == nums[mid + 1]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            elif mid % 2 == 0 and mid + 1 < len(nums):\n",
    "                if nums[mid] != nums[mid + 1]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        return nums[left]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right)// 2\n",
    "            if 0< mid <len(nums) - 1:\n",
    "                if nums[mid - 1]< nums[mid] < nums[mid + 1]:\n",
    "                    return nums[mid]\n",
    "                elif mid % 2 == 0:\n",
    "                    if nums[mid] == nums[mid + 1]:\n",
    "                        left = mid + 2\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "\n",
    "                else:\n",
    "                    if nums[mid] == nums[mid + 1]:\n",
    "                        right = mid\n",
    "                    else:\n",
    "                        left = mid + 1\n",
    "            elif mid == 0:\n",
    "                return nums[0]\n",
    "            else:\n",
    "                return nums[len(nums) - 1]\n",
    "                \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for n in nums:\n",
    "            ans^=n\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, s: List[int]) -> int:\n",
    "        st = ['0']\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if st[-1] == s[i]:\n",
    "                st.pop()\n",
    "                continue\n",
    "            else:\n",
    "                st.append(s[i])\n",
    "\n",
    "        return st[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        for i in nums:\n",
    "            res = res ^ i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        # (dd)s  返回结果下标一定是偶数\n",
    "        n=len(nums)\n",
    "        left=0\n",
    "        right=n-1\n",
    "\n",
    "        # (xx)m(mxx)s\n",
    "        #    s(m)m(xx)\n",
    "        while left<=right:\n",
    "            if left==right:\n",
    "                return nums[left]\n",
    "            mid=left+(right-left)//2\n",
    "            if mid%2==0:\n",
    "                if nums[mid]==nums[mid+1]:\n",
    "                    left=mid\n",
    "                else:\n",
    "                    right=mid\n",
    "            else: # xx(m)ms\n",
    "                if nums[mid]==nums[mid-1]:\n",
    "                    left=mid+1\n",
    "                else:  # s m (m)\n",
    "                    right=mid-1\n",
    "        return nums[left]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        def binarySearch(start, end):\n",
    "            if start >= end:\n",
    "                return nums[start]\n",
    "            mid_id = start + end >> 1\n",
    "            if nums[mid_id] == nums[mid_id - 1]:\n",
    "                if (mid_id - start) % 2 == 0:\n",
    "                    return binarySearch(start, mid_id - 2)\n",
    "                else:\n",
    "                    return binarySearch(mid_id + 1, end)\n",
    "            elif nums[mid_id] == nums[mid_id + 1]:\n",
    "                if (mid_id - start) % 2 == 0:\n",
    "                    return binarySearch(mid_id + 2, end)\n",
    "                else:\n",
    "                    return binarySearch(start, mid_id - 1)\n",
    "            else:\n",
    "                return nums[mid_id]\n",
    "\n",
    "        return binarySearch(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        for num in nums:\n",
    "            cnt = nums.count(num)\n",
    "            if cnt == 1:\n",
    "                return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            res ^= i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, n-1\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if nums[mid-1] == nums[mid]:\n",
    "                if (r - mid) % 2 == 0: # right not possible\n",
    "                    r = mid - 2\n",
    "                else:\n",
    "                    l = mid + 1 # at right side\n",
    "            elif nums[mid] == nums[mid+1]:\n",
    "                if (r - (mid+1)) % 2 == 0: \n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 2\n",
    "            else:\n",
    "                return nums[mid]\n",
    "        \n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        counts = collections.Counter(nums)\n",
    "        for k, v in counts.items():\n",
    "            if v == 1:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        l=0\n",
    "        r=len(nums)-1\n",
    "        if r==0:\n",
    "            return nums[0]\n",
    "        while l<r:\n",
    "            mid= l + ((r-l)>>1)\n",
    "            if (mid-l)%2 ==1:\n",
    "                if nums[mid]==nums[mid-1]:\n",
    "                    l=mid+1\n",
    "                elif nums[mid]==nums[mid+1]:\n",
    "                    r=mid-1\n",
    "                else:\n",
    "                    return nums[mid]\n",
    "            else:#(mid-l)%2==0\n",
    "                if nums[mid]==nums[mid-1]:\n",
    "                    r=mid-2\n",
    "                elif nums[mid]==nums[mid+1]:\n",
    "                    l=mid+2\n",
    "                else:\n",
    "                    return nums[mid]\n",
    "        return nums[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        lens = len(nums)\n",
    "        l, r = 0, lens - 1\n",
    "        while l <= r:\n",
    "            ind = (l + r) >> 1\n",
    "\n",
    "            if nums[ind] != (nums[ind + 1] if ind + 1 < lens else float(\"inf\")) and nums[ind] != (\n",
    "            nums[ind - 1] if ind - 1 > -1 else float\n",
    "                (\"inf\")):\n",
    "                return nums[ind]\n",
    "\n",
    "            lefts = ind - l + 1\n",
    "            rights = r - ind\n",
    "\n",
    "            if ind + 1 < lens and nums[ind] == nums[ind + 1]:\n",
    "                ind += 1\n",
    "                lefts += 1\n",
    "                rights -= 1\n",
    "\n",
    "            if lefts % 2:\n",
    "                r = ind - 2\n",
    "\n",
    "            if rights % 2:\n",
    "                l = ind + 1\n",
    "\n",
    "        return nums[r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        \n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            n = len(nums)\n",
    "            mid = n//2\n",
    "           \n",
    "            if mid%2==1:# liang ce ji shu \n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    res = self.singleNonDuplicate(nums[mid+1:])\n",
    "                elif nums[mid] == nums[mid+1]:\n",
    "                    res = self.singleNonDuplicate(nums[:mid])\n",
    "                else:\n",
    "                    return nums[mid]\n",
    "            else:#liang ce ou shu\n",
    "                if nums[mid] == nums[mid-1]:\n",
    "                    res = self.singleNonDuplicate(nums[:mid-1])\n",
    "                elif nums[mid] == nums[mid+1]:\n",
    "                    res = self.singleNonDuplicate(nums[mid:])\n",
    "                else:\n",
    "                    return nums[mid]\n",
    "            \n",
    "            return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if True:\n",
    "            from functools import reduce\n",
    "            return reduce(lambda x,y: x^y, nums)\n",
    "            \n",
    "\n",
    "        elif False:\n",
    "            if len(nums) ==0 or len(nums)%2==0:\n",
    "                return -1\n",
    "            if len(nums) ==1:\n",
    "                return nums[0]\n",
    "            i=0\n",
    "            while i<len(nums)-1:\n",
    "                if nums[i] == nums[i+1]:\n",
    "                    i+=2\n",
    "                else:\n",
    "                    break\n",
    "            return nums[i]\n",
    "\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def singleNonDuplicate(self, nums: List[int]) -> int:\n",
    "        if len(nums) ==1:\n",
    "            return nums[0]\n",
    "        nums.insert(0,-999)\n",
    "        nums.append(-999)\n",
    "        f1,f2,f3 = 0,1,2\n",
    "        print(nums)\n",
    "        while f3<len(nums):\n",
    "            if nums[f2] != nums[f1] and nums[f2] != nums[f3]:\n",
    "                return nums[f2]\n",
    "            f1 +=1\n",
    "            f2 +=1\n",
    "            f3 +=1\n",
    "        return -1\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
